import java.util.*;

/**
 * 310. 最小高度树
 * https://leetcode-cn.com/problems/minimum-height-trees/
 */
public class Solutions_310 {
    public static void main(String[] args) {
//        int n = 4;
//        int[][] edges = {{1, 0}, {1, 2}, {1, 3}};  // output: {1}

//        int n = 6;
//        int[][] edges = {{3, 0}, {3, 1}, {3, 2}, {3, 4}, {5, 4}};  // output: {3, 4}

        int n = 1;
        int[][] edges = {};  // output: {0}

//        int n = 2;
//        int[][] edges = {{0, 1}};  // output: {0, 1}

        List<Integer> result = findMinHeightTrees(n, edges);
        System.out.println(result);
    }

    /**
     * 解法一：自底向上（13ms）
     * 从叶子节点（入度为 1 的节点）开始向根节点移动
     */
    public static List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> res = new ArrayList<>();
        if (n == 1) {
            res.add(0);
            return res;
        }
        // 遍历 edges，计算每个节点的入度
        // income[3] = 4，说明节点 3 有 4 条边，即节点 3 与 4 个节点之间存在一条边
        int[] income = new int[n];
        // list[3] = {0, 1, 2, 4}，说明节点 3 与 4 个节点 {0, 1, 2, 4} 之间存在一条边
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(new ArrayList<>());
        }
        // 遍历 edges，统计出每个节点的入度，以及记录下每个节点的关联节点（可能是其父节点，也可能是其子节点）
        for (int[] edge : edges) {
            int a = edge[0], b = edge[1];
            income[a] ++;
            income[b] ++;

            list.get(a).add(b);
            list.get(b).add(a);
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < income.length; i++) {
            // 入度为 1 的节点，作为叶子节点入队
            if (income[i] == 1) {
                queue.add(i);
            }
        }

        // 依次取出叶子节点（叶子节点被“砍掉”后，若叶子节点的父节点仅剩下一个节点，那么父节点成为叶子节点）
        // 最终剩余的叶子节点，只可能为一个，或者两个
        while (!queue.isEmpty()) {
            // 新一批的叶子节点
            res = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int node = queue.poll();
                res.add(node);
                List<Integer> relNode = list.get(node);
                for (int j : relNode) {
                    // “砍断”当前叶子节点 node 与其父节点之间的一条边（即父节点的入度 - 1）
                    income[j] --;
                    if (income[j] == 1) {
                        // 关键：入度为 1（只剩一条边），那么认为节点 j 是一个叶子节点，入队吧
                        queue.add(j);
                    }
                }
            }
        }
        return res;
    }

    /**
     * 解法二：自顶向下（超时）
     * 计算每个节点作为根节点时，树的高度
     */
    public static List<Integer> findMinHeightTrees2(int n, int[][] edges) {
        List<Integer> res = new ArrayList<>();
        if (n == 1) {
            res.add(0);
            return res;
        }
        // 记录最小高度
        int min = Integer.MAX_VALUE;
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            int a = edge[0], b = edge[1];
            list.get(a).add(b);
            list.get(b).add(a);
        }
        Queue<Integer> queue = null;
        boolean[] visited = null;
        // 将 [0, n-1] 的节点，作为根节点，计算高度
        for (int i = 0; i < n; i++) {
            queue = new LinkedList<>();
            visited = new boolean[n];
            queue.add(i);
            int cur = 0;
            // 层层迭代
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int j = 0; j < size; j++) {
                    int node = queue.poll();
                    visited[node] = true;
                    List<Integer> relNodes = list.get(node);
                    for (int k : relNodes) {
                        if (!visited[k]) {
                            // 未访问过
                            queue.add(k);
                        }
                    }
                }
                if (!queue.isEmpty()) {
                    // 当前节点还存在子节点，说明存在下一层
                    cur ++;
                }
            }
            if (cur < min) {
                // 更新最小值
                res = new ArrayList<>();
                min = cur;
            }
            if (cur == min) {
                // 相同的最小高度
                res.add(i);
            }
        }
        return res;
    }
}
